package q435_eraseOverlapIntervals;

import java.util.Arrays;
import java.util.Comparator;

public class Solution_1 {
    /*
    如果使用贪心算法
    首先要明确此题具有的四个问题：
    难点⼀：⼀看题就有感觉需要排序，但究竟怎么排序，按左边界排还是右边界排。
    难点⼆：排完序之后如何遍历，如果没有分析好遍历顺序，那么排序就没有意义了。
    难点三：直接求重复的区间是复杂的，转⽽求最⼤⾮重复区间个数。
    难点四：求最⼤⾮重复区间个数时，需要⼀个分割点来做标记

    1 我们的排序方式与遍历的顺序直接相联系，此题我们使用按照右侧边界排序，然后从左向右遍历
    2 按照右边界排序，就要从左向右遍历，因为右边界越⼩越好，只要右边界越⼩，留给下⼀个区间的空间就越⼤，所以从左向右遍历，优先选右边界⼩的。
    3 来按照右边界排序，从左向右记录⾮交叉区间的个数。最后⽤区间总数减去⾮交叉区间的个数就是需要移除的区间个数了。
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        // 先按右边界进行排序
        Arrays.sort(intervals, Comparator.comparingInt(p -> p[1]));

        int count = 1; // 记录⾮交叉区间的个数
        int end = intervals[0][1]; // 记录区间分割点

        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间的起点 大于等于我们所记录的上个区间的终点 代表两个区间没有重合
            // 此时更新end为该区间的终点 并且count++
            // 如果有重合 意味着end将一直不更新 一直记录的是最小的一个右边界
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.length - count;
    }
}
